package com.github.hgkmail.hello.leetcode101.binarysearch;

//二分查找有2种写法：
//左闭右闭(r=len-1 且 l≤r)
//左闭右开（r=len 且 l<r）
public class LC34FindFirstAndLastPositionOfElementInSortedArray {
    /**
     * 左闭右闭 Right Close（推荐）
     * @param lower true：≥，false：＞
     * @return 下标
     */
    public int binarySearchRC(int[] nums, int target, boolean lower) {
        int l=0;
        int r=nums.length-1; //取得到
        int mid;
        while (l<=r) { //等号
            mid=l+(r-l)/2;
            boolean compare=lower ? nums[mid] >= target : nums[mid]>target;
            if (compare) {
                r=mid-1; //mid-1
            } else {
                l=mid+1;
            }
        }
        //大于等于返回l，小于等于返回r
        return l;
    }

    /**
     * 左闭右开 Right Open
     * @param lower true：≥，false：＞
     * @return 下标
     */
    public int binarySearchRO(int[] nums, int target, boolean lower) {
        int l=0;
        int r=nums.length; //取不到
        int mid;
        while (l<r) { //没有等号
            mid=l+(r-l)/2;
            boolean compare = lower ? nums[mid] >= target : nums[mid]>target;
            if (compare) {
                r=mid; //mid
            } else {
                l=mid+1;
            }
        }
        //大于等于返回l，小于等于返回r
        return l;
    }

    public int[] searchRange(int[] nums, int target) {
        int lowerIndex = binarySearchRC(nums, target, true);
        int upperIndex = binarySearchRC(nums, target, false);
        if (lowerIndex>=nums.length || nums[lowerIndex]!=target) {
            return new int[]{-1,-1};
        }
        return new int[]{lowerIndex, upperIndex-1};
    }

    public static void main(String[] args) {
        System.out.println(new LC34FindFirstAndLastPositionOfElementInSortedArray().binarySearchRC(new int[]{5,7,7,8,8,10}, 8, true));
        System.out.println(new LC34FindFirstAndLastPositionOfElementInSortedArray().binarySearchRC(new int[]{5,7,7,8,8,10}, 8, false));

        System.out.println(new LC34FindFirstAndLastPositionOfElementInSortedArray().binarySearchRO(new int[]{5,7,7,8,8,10}, 8, true));
        System.out.println(new LC34FindFirstAndLastPositionOfElementInSortedArray().binarySearchRO(new int[]{5,7,7,8,8,10}, 8, false));
    }
}
